package _02_第二季._01_排序;

import java.util.ArrayList;
import java.util.List;

public class ShellSort07<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        List<Integer> stepSequence = shellStepSequence();
        for (Integer step : stepSequence) {
            sort(step);
        }
    }

    /**
     * 分成step列进行排序
     * 内部因为逆序对越来越少，使用插入排序
     * @param step
     */
    private void sort(int step){
        for(int col = 0;col<step;++col){
            for(int begin = col+step; begin<array.length;begin += step){
                int cur = begin;
                while(cur > col && cmp(cur,cur - step)<0){
                    swap(cur,cur-step);
                    cur -= step;
                }
            }
        }
    }


    /*
        生成步长序列
     */
    private List<Integer> shellStepSequence(){
        List<Integer> list = new ArrayList<>();
        int step = array.length;
        while((step >>=1)>0){
            list.add(step);
        }
        return list;
    }
}
